GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>MapReduce</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">MapReduce</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>MapReduce</b> ist ein vom Unternehmen <a href="Google_Inc." class="mw-redirect" title="Google Inc.">Google Inc.</a> eingeführtes Programmiermodell für <a href="Nebenl%C3%A4ufigkeit" title="Nebenläufigkeit">nebenläufige</a> Berechnungen über (mehrere <a href="Petabyte" class="mw-redirect" title="Petabyte">Petabyte</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>) große Datenmengen auf <a href="Computercluster" class="mw-redirect" title="Computercluster">Computerclustern</a>. <i>MapReduce</i> ist auch der Name einer Implementierung des Programmiermodells in Form einer Software-Bibliothek.

Beim MapReduce-Verfahren werden die Daten in drei Phasen verarbeitet (Map, Shuffle, Reduce), von denen zwei durch den Anwender spezifiziert werden (Map und Reduce). Dadurch lassen sich Berechnungen parallelisieren und auf mehrere Rechner verteilen. Bei sehr großen Datenmengen ist die Parallelisierung unter Umständen schon deshalb erforderlich, weil die Datenmengen für einen einzelnen Prozess (und das ausführende Rechnersystem) zu groß sind.

</p><p>Das Programmiermodell wurde durch die in der <a href="Funktionale_Programmierung" title="Funktionale Programmierung">funktionalen Programmierung</a> häufig verwendeten Funktionen <i>map</i> und <i>reduce</i> inspiriert,<sup id="cite_ref-map_2-0" class="reference"><a href="#cite_note-map-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> auch wenn die Arbeitsweise der Bibliothek davon abweicht.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> 2010 wurde für MapReduce ein US-Patent erteilt.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Der wesentliche Beitrag von MapReduce ist jedoch das zu Grunde liegende System, das die Berechnungen stark parallelisiert, die Reorganisation der Daten im Shuffle-Schritt optimiert, und automatisch auf Fehler im Cluster reagieren kann, wie beispielsweise den Ausfall von kompletten Knoten.

</p>

<div class="mw-heading mw-heading2"><h2 id="Arbeitsweise">Arbeitsweise</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Illustration_des_Datenflusses">Illustration des Datenflusses</h3></div>

</p><p>Das obige Bild illustriert den Datenfluss bei der MapReduce-Berechnung.

</p>

<ul><li>Map-Phase:

<ul><li>Die Eingabedaten <i>(D, A, T, A)</i> werden auf eine Menge von Map-Prozessen verteilt (illustriert durch bunte Rechtecke), welche jeweils die vom Nutzer bereitgestellte Map-Funktion berechnen.</li>

<li>Die Map-Prozesse werden idealerweise parallel ausgeführt.</li>

<li>Jede dieser Map-Instanzen legt Zwischenergebnisse ab (illustriert durch pinkfarbene Sterne).</li>

<li>Von jeder Map-Instanz fließen Daten in eventuell verschiedene Zwischenergebnisspeicher.</li></ul></li>

<li>Shuffle-Phase:

<ul><li>Die Zwischenergebnisse werden gemäß den Ausgabeschlüsseln, die von der Map-Funktion produziert wurden, neu verteilt, sodass alle Zwischenergebnisse mit demselben Schlüssel im nächsten Schritt auf demselben Computersystem verarbeitet werden.</li></ul></li>

<li>Reduce-Phase:

<ul><li>Für jeden Satz an Zwischenergebnissen berechnet jeweils genau ein Reduce-Prozess (illustriert durch violette Rechtecke) die vom Nutzer bereitgestellte Reduce-Funktion und damit die Ausgabedaten (illustriert durch violette Kreise <i>X, Y</i> und <i>Z</i>).</li>

<li>Die Reduce-Prozesse werden idealerweise ebenfalls parallel ausgeführt.</li></ul></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Definition_der_MapReduce-Funktion">Definition der MapReduce-Funktion</h3></div>

<p>Die MapReduce-Bibliothek realisiert eine <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Funktion</a>, welche aus einer <a href="Liste_(Datenstruktur)" title="Liste (Datenstruktur)">Liste</a> von <a href="Schl%C3%BCssel-Wert-Paar" class="mw-redirect" title="Schlüssel-Wert-Paar">Schlüssel-Wert-Paaren</a> (Eingabeliste) eine neue Liste von Schlüssel-Wert-Paaren (Ausgabeliste) berechnet:

</p>

<mtr>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathrm {MapReduce} :(K\times V)^{*}&\to (L\times W)^{*}\\{\lbrack (k_{1},v_{1}),\ldots ,(k_{n},v_{n})\rbrack }&\mapsto \lbrack (l_{1},w_{1}),\ldots ,(l_{m},w_{m})\rbrack \end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/17428e5fd3803726ee0b88394abe5ea7076e79b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:50.17ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}\mathrm {MapReduce} :(K\times V)^{*}&\to (L\times W)^{*}\\{\lbrack (k_{1},v_{1}),\ldots ,(k_{n},v_{n})\rbrack }&\mapsto \lbrack (l_{1},w_{1}),\ldots ,(l_{m},w_{m})\rbrack \end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Erläuterung:

</p>

<ul><li>Die Mengen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> enthalten <b>Schlüssel</b>, die Mengen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"></span> enthalten <b>Werte</b>.</li>

<li>Alle Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in K}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3846561ca971f4b17e10153d1f996e08e5ac192.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.118ex; height:2.176ex;" alt="{\displaystyle k\in K}" loading="lazy"></span> sind vom gleichen <a href="Datentyp" title="Datentyp">Typ</a>, z. B. Strings.</li>

<li>Alle Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l\in L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l\in L}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4af31b518b8600dc8ff15041dc353769574d4631.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.117ex; height:2.176ex;" alt="{\displaystyle l\in L}" loading="lazy"></span> sind vom gleichen Typ, z. B. ganze Zahlen.</li>

<li>Alle Werte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99886ebbde63daa0224fb9bf56fa11b3c8a6f4fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.756ex; height:2.176ex;" alt="{\displaystyle v\in V}" loading="lazy"></span> sind vom gleichen Typ, z. B. Atome.</li>

<li>Alle Werte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in W}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ff0b62771fb4b163c4f1260be1c39768e7173e3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.94ex; height:2.176ex;" alt="{\displaystyle w\in W}" loading="lazy"></span> sind vom gleichen Typ, z. B. Gleitkommazahlen.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> Mengen sind, so ist mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\times B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\times B}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65f31ae45b0098f06b5d22c38d317eb097a88fa9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.348ex; height:2.176ex;" alt="{\displaystyle A\times B}" loading="lazy"></span> die Menge aller Paare <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a,b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a,b)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d7e5710198f33b00695903460983021e75860e2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.071ex; height:2.843ex;" alt="{\displaystyle (a,b)}" loading="lazy"></span> gemeint, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a97387981adb5d65f74518e20b6785a284d7abd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.814ex; height:2.176ex;" alt="{\displaystyle a\in A}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\in B}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61dbfba9ff608c8700a30596649d98dcc6147d86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.602ex; height:2.176ex;" alt="{\displaystyle b\in B}" loading="lazy"></span> (<a href="Kartesisches_Produkt" title="Kartesisches Produkt">kartesisches Produkt</a>).</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> eine Menge ist, so ist mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b6d760e72a9f5f578f8ba166127f0713d56dc589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.553ex; height:2.343ex;" alt="{\displaystyle M^{*}}" loading="lazy"></span> die Menge aller endlichen Listen mit Elementen aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> gemeint (angelehnt an den <a href="Kleene-Stern" class="mw-redirect" title="Kleene-Stern">Kleene-Stern</a>) – die Liste kann auch leer sein.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Definition_der_Map-_und_Reduce-Funktionen">Definition der Map- und Reduce-Funktionen</h3></div>

<p>Der Nutzer konfiguriert die Bibliothek über die Bereitstellung der beiden Funktionen Map und Reduce, die wie folgt definiert sind:

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathrm {Map} :K\times V&\to (L\times W)^{*}\\(k,v)&\mapsto \lbrack (l_{1},x_{1}),\ldots ,(l_{r_{k}},x_{r_{k}})\rbrack \end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/22ac2973a81d114ce2d092f45e63f8790841ca62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.28ex; margin-bottom: -0.225ex; width:39.562ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}\mathrm {Map} :K\times V&\to (L\times W)^{*}\\(k,v)&\mapsto \lbrack (l_{1},x_{1}),\ldots ,(l_{r_{k}},x_{r_{k}})\rbrack \end{aligned}}}" loading="lazy"></span></dd></dl>

<p>bzw.

</p>

<mtr>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathrm {Reduce} :L\times W^{*}&\to X^{*}\\\left(l,{\lbrack y_{1},\ldots ,y_{s_{l}}\rbrack }\right)&\mapsto \lbrack w_{1},\ldots ,w_{m_{l}}\rbrack \end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e60846d9bacd5888efd1c0db4e2fb9481e5ce1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:34.772ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}\mathrm {Reduce} :L\times W^{*}&\to X^{*}\\\left(l,{\lbrack y_{1},\ldots ,y_{s_{l}}\rbrack }\right)&\mapsto \lbrack w_{1},\ldots ,w_{m_{l}}\rbrack \end{aligned}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Map-Phase">Map-Phase</h3></div>

<ul><li>Map bildet ein Paar, bestehend aus einem Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> und einem Wert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span>, auf eine Liste von neuen Paaren <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l_{r},x_{r})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l_{r},x_{r})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/419a4e53553e31f0cdc8a11fbcac3e5fa1101e19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.814ex; height:2.843ex;" alt="{\displaystyle (l_{r},x_{r})}" loading="lazy"></span> ab, welche die Rolle von <b>Zwischenergebnissen</b> spielen. Die Werte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{r}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/044e7a8546346e93fcc74c4754233e852dec8f16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.303ex; height:2.009ex;" alt="{\displaystyle x_{r}}" loading="lazy"></span> sind vom gleichen Typ wie die Endergebnisse <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"></span>.</li>

<li>Bei einem neuen Paar <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l,x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l,x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34435631a8c55c741db9485a57176d8a7b4c5fd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.866ex; height:2.843ex;" alt="{\displaystyle (l,x)}" loading="lazy"></span> verweist der von Map vergebene Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> dabei auf eine Liste <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{l}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0dc7062014f0e0f99427475fb2ef299e2a63b0d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.08ex; height:2.509ex;" alt="{\displaystyle T_{l}}" loading="lazy"></span> von Zwischenergebnissen, in welcher der von Map berechnete Wert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> gesammelt wird.</li>

<li>Die Bibliothek ruft für jedes Paar in der Eingabeliste die Funktion Map auf.</li>

<li>All diese Map-Berechnungen sind voneinander unabhängig, so dass man sie nebenläufig und verteilt auf einem Computercluster ausführen kann.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Shuffle-Phase">Shuffle-Phase</h3></div>

<ul><li>Bevor die Reduce-Phase starten kann, müssen die Ergebnisse der Map-Phase nach ihrem neuen Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> in Listen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{l}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0dc7062014f0e0f99427475fb2ef299e2a63b0d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.08ex; height:2.509ex;" alt="{\displaystyle T_{l}}" loading="lazy"></span> gruppiert werden.</li>

<li>Wenn Map- und Reduce-Funktionen nebenläufig und verteilt ausgeführt werden, wird hierfür ein koordinierter Datenaustausch notwendig.</li>

<li>Die Performanz eines Map-Reduce-Systems hängt maßgeblich davon ab, wie effizient die Shuffle-Phase implementiert ist.</li>

<li>Der Nutzer wird in der Regel nur über die Gestaltung der Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> auf die Shuffle-Phase Einfluss nehmen. Daher reicht es, sie einmalig gut zu optimieren, und zahlreiche Anwendungen können hiervon profitieren.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Reduce-Phase">Reduce-Phase</h3></div>

<ul><li>Sind alle Map-Aufrufe erfolgt bzw. liegen alle Zwischenergebnisse in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{l}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0dc7062014f0e0f99427475fb2ef299e2a63b0d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.08ex; height:2.509ex;" alt="{\displaystyle T_{l}}" loading="lazy"></span> vor, so ruft die Bibliothek für jede Zwischenwertliste die Funktion Reduce auf, welche daraus eine Liste von Ergebniswerten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{j}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/326f4828cd2d8b281d5837f977d435d47450a191.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.574ex; height:2.343ex;" alt="{\displaystyle w_{j}}" loading="lazy"></span> berechnet, die von der Bibliothek in der Ausgabeliste als Paare <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l,w_{j})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l,w_{j})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdb7145f6ca7f7aba34146e6233afa1e898dd9b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.11ex; height:3.009ex;" alt="{\displaystyle (l,w_{j})}" loading="lazy"></span> gesammelt werden.</li>

<li>Auch die Aufrufe von Reduce können unabhängig auf verschiedene Prozesse im Computercluster verteilt werden.</li></ul>

<p>Anmerkung: Diese Darstellung war etwas vereinfacht, denn in der Regel wird die Steuerung des MapReduce Verfahrens eine Anzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> von Reduce-Prozessen anstreben, so dass, wenn es für mehr als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> verschiedene Schlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> Zwischenergebnisse <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l,x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l,x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34435631a8c55c741db9485a57176d8a7b4c5fd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.866ex; height:2.843ex;" alt="{\displaystyle (l,x)}" loading="lazy"></span> gibt, Zwischenergebnisse <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l,x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l,x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34435631a8c55c741db9485a57176d8a7b4c5fd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.866ex; height:2.843ex;" alt="{\displaystyle (l,x)}" loading="lazy"></span> mit verschiedenen Schlüsseln <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> in einer gemeinsamen Liste gespeichert werden. Die entsprechenden Paare werden vor der Reduce-Berechnung nach Schlüsseln sortiert.

</p>

<div class="mw-heading mw-heading3"><h3 id="Combine-Phase">Combine-Phase</h3></div>

<p>Optional kann vor der Shuffle-Phase noch eine Combine-Phase erfolgen. Diese hat in der Regel die gleiche Funktionalität wie die Reducefunktion, wird aber auf dem gleichen Knoten wie die Map-Phase ausgeführt. Dabei geht es darum, die Datenmenge, die in der Shuffle-Phase verarbeitet werden muss, und damit die Netzwerklast zu reduzieren.<sup id="cite_ref-map_2-1" class="reference"><a href="#cite_note-map-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Der Sinn der Combine-Phase erschließt sich sofort bei der Betrachtung des <a href="#Beispiel:_Verteilte_Häufigkeitsanalyse_mit_MapReduce">Wordcount-Beispiels</a>: Auf Grund der unterschiedlichen Häufigkeit von Wörtern in natürlicher Sprache, würde bei einem deutschen Text beispielsweise sehr oft eine Ausgabe der Form ("und", 1) erzeugt (gleiches gilt für Artikel und Hilfsverben). Durch die Combine-Phase wird nun aus 100 Nachrichten der Form ("und", 1) lediglich eine Nachricht der Form ("und", 100). Dies kann die Netzwerkbelastung signifikant reduzieren, ist aber nicht in allen Anwendungsfällen möglich.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel:_Verteilte_Häufigkeitsanalyse_mit_MapReduce"><span id="Beispiel:_Verteilte_H.C3.A4ufigkeitsanalyse_mit_MapReduce"></span>Beispiel: Verteilte Häufigkeitsanalyse mit MapReduce</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Problem">Problem</h3></div>

<p>Man möchte für umfangreiche Texte herausfinden, wie oft welche Wörter vorkommen.

</p>

<div class="mw-heading mw-heading3"><h3 id="Angabe_der_Map-_und_Reduce-Funktionen">Angabe der Map- und Reduce-Funktionen</h3></div>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> map(String name, String document):

// name: document name ("key")

// document: document contents ("value")

for each word w in document:

EmitIntermediate(w, 1);

reduce(String word, Iterator partialCounts):

// word: a word ("key")

// partialCounts: a list of aggregated partial counts ("values")

// for 'word'

int result = 0;

for each v in partialCounts:

result += v;

Emit(word, result);

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Map-Phase_2">Map-Phase</h3></div>

<ul><li>Map bekommt jeweils einen Dokumentnamen <i>name</i> und ein Dokument <i>document</i> als <a href="Zeichenkette" title="Zeichenkette">Zeichenkette</a> übergeben.</li>

<li>Map durchläuft das Dokument Wort für Wort.</li>

<li>Jedes Mal, wenn ein Wort <i>w</i> angetroffen wird, wandert eine 1 in die <i>w</i>-Zwischenergebnisliste (falls diese noch nicht existiert, wird sie angelegt).</li>

<li>Ist man mit allen Wörtern durch und hat der Text insgesamt <i>n</i> verschiedene Wörter, so endet die Map-Phase mit <i>n</i> Zwischenergebnislisten, jede für ein anderes Wort sammelnd, welche so viele 1-Einträge enthält, wie das entsprechende Wort im Dokument gefunden wurde.</li>

<li>Eventuell liefen viele Map-Instanzen gleichzeitig, falls der Bibliothek mehrere Wörter und Dokumente übergeben wurden.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Shuffle-Phase_2">Shuffle-Phase</h3></div>

<ul><li>Die Zwischenergebnislisten von mehreren Prozessen / Systemen für das gleiche Wort <i>w</i> werden zusammengefasst, und auf die Systeme für die Reducer verteilt.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Reduce-Phase_2">Reduce-Phase</h3></div>

<ul><li>Reduce wird für das Wort <i>word</i> und die Zwischenergebnisliste <i>partialCounts</i> aufgerufen.</li>

<li>Reduce durchläuft die Zwischenergebnisliste und addiert alle gefundenen Zahlen auf.</li>

<li>Die Summe result wird an die Bibliothek zurückgegeben, sie enthält, wie oft das Wort <i>word</i> in allen Dokumenten gefunden wurde.</li>

<li>Die Zwischenergebnisse konnten parallel, durch gleichzeitige Reduce-Aufrufe, berechnet werden.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Insgesamt">Insgesamt</h3></div>

<ul><li>Aus einer Liste von Dokumentnamen und Dokumenten wird eine Liste von Worten und Worthäufigkeiten generiert.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Beispielhafte_Berechnung">Beispielhafte Berechnung</h3></div>

<p>Zum Beispiel wäre folgende Berechnung auf einem <a href="Das_Lied_von_der_Glocke" title="Das Lied von der Glocke">klassischen Text</a> denkbar:

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> Text = "Fest gemauert in der Erden

Steht die Form, aus Lehm gebrannt.

Heute muß die Glocke werden,

Frisch, Gesellen! seid zur Hand.

Von der Stirne heiß

Rinnen muß der Schweiß,

Soll das Werk den Meister loben,

Doch der Segen kommt von oben."

</pre></div>

<p>Der Text wird in Sätze aufgeteilt, dabei bietet sich eine <a href="Normalisierung_(Text)" title="Normalisierung (Text)">Normalisierung</a> an, indem man alles klein schreibt und die Satzzeichen entfernt:

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> Eingabeliste = [ (satz_1, "fest gemauert in der erden steht die form aus lehm gebrannt"),

(satz_2, "heute muß die glocke werden frisch gesellen seid zur hand"),

(satz_3, "von der stirne heiß rinnen muß der schweiß soll das werk den meister loben doch der segen kommt von oben") ]

</pre></div>

<p>Die Eingabeliste hat drei Paare als Elemente, wir können daher drei Map-Prozesse starten:

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> P1 = Map(satz_1, "fest gemauert in der erden steht die form aus lehm gebrannt")

P2 = Map(satz_2, "heute muß die glocke werden frisch gesellen seid zur hand")

P3 = Map(satz_3, "von der stirne heiß rinnen muß der schweiß soll das werk den meister loben doch der segen kommt von oben")

</pre></div>

<p>Die Map-Aufrufe generieren diese Zwischenergebnispaare:

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> P1 = [ ("fest", 1), ("gemauert", 1), ("in", 1), ("der", 1), ("erden", 1),

("steht", 1), ("die", 1), ("form", 1), ("aus", 1), ("lehm, 1),

("gebrannt", 1) ]

P2 = [ ("heute", 1), ("muß", 1), ("die", 1), ("glocke", 1), ("werden", 1),

("frisch", 1), ("gesellen", 1), ("seid", 1), ("zur", 1), ("hand", 1) ]

P3 = [ ("von", 1), ("der", 1), ("stirne", 1), ("heiß", 1), ("rinnen", 1),

("muß, 1), ("der", 1), ("schweiß", 1), ("soll", 1), ("das", 1),

("werk", 1), ("den", 1), ("meister", 1), ("loben", 1), ("doch", 1),

("der", 1), ("segen", 1), ("kommt", 1), ("von", 1), ("oben", 1) ]

</pre></div>

<p>Die Map-Prozesse liefern ihre Paare an die MapReduce-Bibliothek, welche diese in den Zwischenergebnislisten sammelt. Parallel könnte folgendes geschehen (Die gleiche Taktung der 3 Map-Prozesse ist unrealistisch, tatsächlich überlappen sich die Ausführungen. Die T_wort-Listen sind lokal pro Map-Prozess vorhanden und werden <b>nicht</b> zwischen den Schritten synchronisiert):

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> 1. Iteration:

P1: T_fest = [ 1 ] (neu)

P2: T_heute = [ 1 ] (neu)

P3: T_von = [ 1 ] (neu)

2. Iteration:

P1: T_gemauert = [ 1 ] (neu)

P2: T_muß = [ 1 ] (neu)

P3: T_der = [ 1 ] (neu)

3. Iteration:

P1: T_in = [ 1 ] (neu)

P2: T_die = [ 1 ] (neu)

P3: T_stirne = [ 1 ] (neu)

</pre></div>

<p>Im vierten Schritt sieht man, dass Zwischenergebnislisten lokal für jeden Map-Prozess existieren und nicht global wiederverwendet werden können:

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> 4. Iteration:

P1: T_der = [ 1 ] (neu, der 1. Map-Prozess hat noch kein T_der, nur P3)

P2: T_glocke = [ 1 ] (neu)

P3: T_heiss = [ 1 ] (neu)

5. Iteration

P1: T_erden = [ 1 ] (neu)

P2: T_werden = [ 1 ] (neu)

P3: T_rinnen = [ 1 ] (neu)

6. Iteration

P1: T_steht = [ 1 ] (neu)

P2: T_frisch = [ 1 ] (neu)

P3: T_muß = [ 1 ] (neu, der 3. Map-Prozess hat noch kein T_muß, nur P2)

</pre></div>

<p>Im siebten Schritt kommt dann zum ersten Mal vor, dass ein weiteres Vorkommen in einer bereits angelegten Zwischenergebnisliste gesammelt wird:

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> 7. Schritt

P1: T_die = [ 1 ] (neu, der 1. Map-Prozess hat noch kein T_die)

P2: T_gesellen = [ 1 ] (neu)

P3: T_der = [ 1, 1 ] (beim 3. Map-Prozess seit Iteration 2 vorhandene Liste verwenden)

</pre></div>

<p>usw.

</p><p>Nach 21 Schritten sind alle drei Map-Prozesse mit ihrer Arbeit fertig, die Map-Phase endet und es beginnt die Reduce-Phase.

Die Zwischenergebnislisten, die von verschiedenen Map-Prozessen zu demselben Wort angelegt wurden, werden zusammengefügt.

Für jede der entstandenen Zwischenergebnislisten (hier sortiert aufgeführt)

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> reduce

T_der = [ 1 ] ++ [ 1, 1, 1 ] -> [ 4 ]

T_die = [ 1 ] ++ [ 1 ] -> [ 2 ]

T_fest = [ 1 ] -> [ 1 ]

T_gemauert = [ 1 ] -> [ 1 ]

T_glocke = [ 1 ] -> [ 1 ]

T_heiss = [ 1 ] -> [ 1 ]

T_heute = [ 1 ] -> [ 1 ]

T_in = [ 1 ] -> [ 1 ]

T_muß = [ 1 ] ++ [ 1 ] -> [ 2 ]

T_stirne = [ 1 ] -> [ 1 ]

T_von = [ 1, 1 ] -> [ 2 ]

.

. (für alle verschiedenen T-Listen)

</pre></div>

<p>können wir parallel einen Reduce-Prozess starten, der jeweils die Elemente aufzählt.

Das Ergebnis von MapReduce sieht in etwa so aus:

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span> Ausgabeliste = [ ("fest", 1), ("heute", 1), ("von", 2), ("gemauert", 1),

("muß", 2), ("der", 4), ("in", 1), ("die", 2), .. ]

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Weitere_Beispiele">Weitere Beispiele</h2></div>

<th>Verfahren

</th>

<th>Map-Funktion

</th>

<th>Reduce-Funktion

</th></tr>

<tr>

<td>Verteiltes <a href="Grep" title="Grep">grep</a></td>

<td>Gibt die gefundene Zeile (hit) in einen Zwischenergebnisspeicher</td>

<td>Reicht durch (<a href="Identische_Abbildung" title="Identische Abbildung">Identische Abbildung</a>, genauer: <a href="Projektion_(Mengenlehre)" title="Projektion (Mengenlehre)">Projektion</a> auf die 2. Komponente)

</td></tr>

<tr>

<td>Umsatzauswertung</td>

<td>Schreibt für jeden Beleg die Artikelnummer und den Betrag in einen Zwischenspeicher</td>

<td>Addiert für jede unterschiedliche Artikelnummer die Beträge zusammen

</td></tr>

<tr>

<td>Datenbanksystem</td>

<td>Liest, filtert und verarbeitet Teilmengen von Datensätzen</td>

<td>Führt Aggregatfunktionen aus

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Verallgemeinerung">Verallgemeinerung</h2></div>

<p>Nachdem das Verfahren 2014 bereits zehn Jahre alt ist, bietet Google seit kurzem eine Erweiterung <i>Cloud Dataflow</i> an, die größere Flexibilität bietet und das <a href="Cloud_Computing" title="Cloud Computing">Cloud Computing</a> noch stärker vorantreiben soll.

</p>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Apache_Hadoop" title="Apache Hadoop">Apache Hadoop</a> – Java-Framework basierend auf dem MapReduce-Algorithmus</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"><span class="mw-default-size" typeof="mw:File"><span title="Commons"></span></span></div><b><span class=""><a class="external text" href="https://commons.wikimedia.org/wiki/Category:MapReduce?uselang=de"><span lang="en">Commons</span>: MapReduce</a></span></b> – Sammlung von Bildern, Videos und Audiodateien</div>

<div class="mw-heading mw-heading3"><h3 id="Fachartikel">Fachartikel</h3></div>

<ul><li><a href="Jeffrey_Dean" class="mw-redirect" title="Jeffrey Dean">Jeffrey Dean</a>, <a href="Sanjay_Ghemawat" title="Sanjay Ghemawat">Sanjay Ghemawat</a>: <i>MapReduce: Simplified Data Processing on Large Clusters</i>, OSDI'04: Sixth Symposium on Operating System Design and Implementation (Dezember 2004), <a rel="nofollow" class="external text" href="https://research.google.com/archive/mapreduce.html">Online</a></li>

<li>Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, Christos Kozyrakis: <a rel="nofollow" class="external text" href="https://csl.stanford.edu/%7Echristos/publications/2007.cmp_mapreduce.hpca.pdf"><i>Evaluating MapReduce for Multi-core and Multiprocessor Systems</i>.</a> (PDF; 353 kB) <a href="Stanford_University" title="Stanford University">Stanford University</a></li>

<li><a rel="nofollow" class="external text" href="https://www.dbms2.com/2008/08/26/why-mapreduce-matters-to-sql-data-warehousing/"><i>Why MapReduce Matters to SQL Data Warehousing</i>.</a> Analyse zur Einführung von MapReduce/SQL seitens Aster Data Systems und Greenplum</li>

<li>Marc de Kruijf, Karthikeyan Sankaralingam: <a rel="nofollow" class="external text" href="https://pages.cs.wisc.edu/~dekruijf/docs/mapreduce-cell.pdf"><i>MapReduce for the Cell B.E. Architecture</i>.</a> (PDF; 528 kB) <a href="University_of_Wisconsin%E2%80%93Madison" title="University of Wisconsin–Madison">University of Wisconsin–Madison</a></li>

<li>Hung-Chih Yang, Ali Dasdan, Ruey-Lung Hsiao, D. Stott Parker: <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?doid=1247480.1247602"><i>Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters</i>.</a> In: <i>Proc. of ACM SIGMOD</i>, 2007, S. 1029–1040 (Dieses Paper zeigt, wie man MapReduce auf relationale Datenverarbeitung ausweitet)</li>

<li>FLuX: Der <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/647742.html"><i>Fault-tolerant</i></a>, <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/546646.html"><i>Load Balancing</i></a> <i>eXchange operator</i> der <a href="UC_Berkeley" class="mw-redirect" title="UC Berkeley">UC Berkeley</a> bietet eine Alternative zu Googles MapReduce, mit <a href="Failover" title="Failover">Failover</a> aber zusätzlichen Implementierungskosten.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Software">Software</h3></div>

<ul><li><a rel="nofollow" class="external text" href="https://hadoop.apache.org/">Apache Hadoop MapReduce</a></li>

<li><a rel="nofollow" class="external text" href="http://discoproject.org/">disco</a> Open-Source-Projekt (Python und Erlang) des <a href="Nokia" title="Nokia">Nokia</a> Research Center</li>

<li><a rel="nofollow" class="external text" href="https://research.microsoft.com/en-us/projects/dryadlinq/">DryadLINQ</a> – MapReduce Implementierung von <a href="Microsoft_Research" title="Microsoft Research">Microsoft Research</a>. Basiert auf <a href="Parallel_Extensions#Parallel_LINQ" title="Parallel Extensions">PLINQ</a> und <a rel="nofollow" class="external text" href="http://research.microsoft.com/en-us/projects/dryad/default.aspx">Dryad</a>.</li>

<li><a rel="nofollow" class="external text" href="http://www.mathworks.de/discovery/matlab-mapreduce-hadoop.html">MATLAB MapReduce</a> ist eine <a href="Hadoop" class="mw-redirect" title="Hadoop">Hadoop</a> fähige Implementierung von <a href="MathWorks" class="mw-redirect" title="MathWorks">MathWorks</a> in <a href="Matlab" title="Matlab">Matlab</a>.</li>

<li><a rel="nofollow" class="external text" href="https://projects.camlcity.org/projects/plasma.html">Plasma MapReduce</a> ist eine Open Source MapReduce Implementierung in <a href="Ocaml" class="mw-redirect" title="Ocaml">Ocaml</a> mit einem eigenen verteilten Dateisystem</li>

<li><a rel="nofollow" class="external text" href="https://doc.qt.io/qt-5/qtconcurrentmap.html">QtConcurrent</a> Open Source C++ MapReduce Implementierung (nicht-verteilt) der <a href="Qt_Development_Frameworks" class="mw-redirect" title="Qt Development Frameworks">Qt Development Frameworks</a> von <a href="Digia" title="Digia">Digia</a></li>

<li><a rel="nofollow" class="external text" href="http://skynet.rubyforge.org/">Skynet</a> <a href="Ruby_(Programmiersprache)" title="Ruby (Programmiersprache)">Ruby</a> Map/Reduce-Bibliothek</li></ul>

<p>PlasmaFS. Plasma MapReduce wurde von Gerd Stolpmann (Darmstadt) entwickelt.

</p>

<ul><li><a rel="nofollow" class="external text" href="https://www.splunk.com/">Splunk.com</a> Data Management und Analyse Engine für Big Data, welche auf MapReduce basiert</li>

<li><a rel="nofollow" class="external text" href="http://www.stratosphere.eu/">Stratosphere</a> PACT Programmiermodell: Erweiterung und Generalisierung des MapReduce Programmiermodells</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

/* start https://de.wikipedia.org/ */

.mw-parser-output .webarchiv-memento a{color:inherit}

/* end https://de.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131019063218/http://news.cnet.com/8301-10784_3-9955184-7.html"><i>Google spotlights data center inner workings</i>.</a> (<span class="webarchiv-memento"><a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a></span> des <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><span class="dewiki-iconexternal"><a class="external text" href="https://redirecter.toolforge.org/?url=http%3A%2F%2Fnews.cnet.com%2F8301-10784_3-9955184-7.html">Originals</a></span> vom 19. Oktober 2013 im <i><a href="Internet_Archive" title="Internet Archive">Internet Archive</a></i>) <small class="archiv-bot"><span class="wp_boppel noviewer" aria-hidden="true" role="presentation"><span typeof="mw:File"><span title="i"></span></span></span> <b>Info:</b> Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.</small><span style="display:none"><a rel="nofollow" class="external text" href="http://IABotmemento.invalid/http://news.cnet.com/8301-10784_3-9955184-7.html">@1</a></span><span style="display:none"><a rel="nofollow" class="external text" href="https://news.cnet.com/8301-10784_3-9955184-7.html">@2</a></span><span style="display:none">Vorlage:Webachiv/IABot/news.cnet.com</span> CNET News, Tech news blog</span>

</li>

<li id="cite_note-map-2"><span class="mw-cite-backlink">↑ <sup><a href="#cite_ref-map_2-0">a</a></sup> <sup><a href="#cite_ref-map_2-1">b</a></sup></span> <span class="reference-text">Jeffrey Dean, Sanjay Ghemawat: <a rel="nofollow" class="external text" href="http://research.google.com/archive/mapreduce.html"><i>MapReduce: Simplified Data Processing on Large Clusters</i>.</a> <a href="Google_Labs" title="Google Labs">Google Labs</a>: “Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages.”</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">Ralf Lämmel (<a href="Microsoft" title="Microsoft">Microsoft</a>): <a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.5859&rep=rep1&type=pdf"><i>Google’s MapReduce Programming Model – Revisited</i>.</a> (PDF)</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text"><span class="cite">Patent <a rel="nofollow" class="external text" href="https://worldwide.espacenet.com/publicationDetails/biblio?locale=de_EP&CC=US&NR=7650331B1&FT=D&KC=B1">US7650331B1</a>: <i>System and method for efficient large-scale data processing.</i> Angemeldet am <span style="white-space:nowrap;">18. Juni 2004</span>, veröffentlicht am <span style="white-space:nowrap;">19. Januar 2010</span>, Anmelder: Google Inc, Erfinder: Jeffrey Dean, Sanjay Ghemawat.</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Apatent&rft_id=US7650331B1&rft.applcc=US&rft.title=System+and+method+for+efficient+large-scale+data+processing&rft.inventor=Jeffrey+Dean%2C+Sanjay+Ghemawat&rft.assignee=Google+Inc&rft.appldate=2004-06-18&rft.pubdate=2010-01-19">‌</span></span>

</li>

</ol>

<div>

Normdaten (Sachbegriff): <a href="Library_of_Congress_Control_Number" title="Library of Congress Control Number">LCCN</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/no2013077469">no2013077469</a></span> | <a href="Virtual_International_Authority_File" title="Virtual International Authority File">VIAF</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://viaf.org/viaf/305041139/">305041139</a></span> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2026-01-05" href="https://de.wikipedia.org/wiki/?title=MapReduce&oldid=263065076">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>